package com.smh;

import org.junit.jupiter.api.Test;

import javax.swing.tree.TreeNode;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Stack;

/**
 * @author shiminghui
 * @date 2025/2/21 9:34
 * @description: TODO
 */
public class _032_二叉树练习 {

    @Test
    public void test1() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);
        System.out.println(isSymmetric(root));
    }


    // 二叉树是否对称
    public boolean isSymmetric(TreeNode root) {
        boolean symmetric = isSymmetric(root.left, root.right);
        return symmetric;
    }

    private boolean isSymmetric(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null || root2 == null) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left);
    }


    // 二叉树的最大深度

    @Test
    public void test2() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);
        root.left.left.left = new TreeNode(5);
        System.out.println(maxDepth(root));
        System.out.println(maxDepth2(root));
        System.out.println(maxDepth3(root));
    }

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }

    public int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        TreeNode flag = null;
        int depth = 0;
        int maxDepth = 0;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.addLast(cur);
                cur = cur.left;
                depth++; // 当前深度加一
            } else {
                TreeNode peek = stack.getLast();
                if (peek.right == null || peek.right == flag) {
                    flag = stack.removeLast();
                    maxDepth = Math.max(maxDepth, depth); // 记录最大深度
                    depth--; // 当前深度减一
                } else {
                    cur = peek.right;
                }
            }
        }
        return maxDepth;
    }

    // 使用层序遍历
    public int maxDepth3(TreeNode root) {
        if (root == null) {
            return 0;
        }
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.add(root);
        int c1 = 1;
        int c2 = 0;
        int depth = 0;
        while (!deque.isEmpty()) {
            for (int i = 0; i < c1; i++) {
                TreeNode treeNode = deque.pollFirst();
                if (treeNode.left != null) {
                    deque.add(treeNode.left);
                    c2++;
                }
                if (treeNode.right != null) {
                    deque.add(treeNode.right);
                    c2++;
                }
            }
            c1 = c2;
            c2 = 0;
            depth++;
        }
        return depth;
    }


    // 求二叉树的最小深度

    @Test
    public void test3() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
//        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
//        root.right.left = new TreeNode(4);
//        root.right.right = new TreeNode(3);
        System.out.println(minDepth(root));
        System.out.println(minDepth2(root));
        System.out.println(minDepth3(root));
    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (left == 0 || right == 0) { // 左右子树有一个为空，则返回不为空的子树的深度
            return Integer.max(left, right) + 1;
        }
        return Integer.min(left, right) + 1;
    }

    // 使用非递归遍历
    public int minDepth2(TreeNode root) {
        if (root == null)
            return 0;
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        TreeNode flag = null;
        int depth = 0;
        int minDepth = Integer.MAX_VALUE;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.addLast(cur);
                cur = cur.left;
                depth++;
            } else {
                TreeNode peek = stack.getLast();
                if (peek.left == null && peek.right == null) { // 遇到叶子节点, 更新最小深度
                    minDepth = Math.min(minDepth, depth);
                    flag = stack.removeLast();
                    depth--;
                } else if (peek.right == null || peek.right == flag) {
                    flag = stack.removeLast();
                    depth--;
                } else {
                    cur = peek.right;
                }
            }
        }
        return minDepth;
    }

    // 使用层序遍历获取二叉树的最小深度
    // 遇到的第一个叶子节点就是最小深度
    public int minDepth3(TreeNode root) {
        if (root == null) {
            return 0;
        }
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.add(root);
        int depth = 1;
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = deque.pollFirst();
                if (treeNode.left != null) {
                    deque.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    deque.add(treeNode.right);
                }
                if (treeNode.left == null && treeNode.right == null) {
                    return depth;
                }
            }
            depth++;
        }
        return depth;
    }

    @Test
    public void test4() {
        int limit = 10;
        for (int i = 0; i < limit; i++) {
            System.out.println("Iteration: " + i);
            // 修改 limit 的值
            limit = 5;
        }
    }

    // 翻转二叉树
    public TreeNode flipTree(TreeNode root) {
        invertTree(root);
        return root;
    }

    public void invertTree(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
    }

    // 根据后缀字符串数组创建二叉树
    @Test
    public void test5() {
        String[] postfix = {"4", "5", "-", "3", "*"};
        TreeNode root = createBinaryTree(postfix);
        System.out.println(root);
    }

    public TreeNode createBinaryTree(String[] postfix) {
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        for (int i = 0; i < postfix.length; i++) {
            if (postfix[i].equals("+") || postfix[i].equals("-") || postfix[i].equals("*") || postfix[i].equals("/")) {
                TreeNode right = deque.pollLast();
                TreeNode left = deque.pollLast();
                TreeNode root = new TreeNode(left, postfix[i], right);
                deque.addLast(root);
                continue;
            }
            deque.addLast(new TreeNode(postfix[i]));
        }
        return deque.pollLast();
    }


    // 根据前序和中序遍历创建二叉树

    @Test
    public void test6() {
        String[] preorder = {"1", "2", "4", "7", "3", "5", "6", "8"};
        String[] inorder = {"4", "7", "2", "1", "5", "3", "8", "6"};
        TreeNode root = createBinaryTree(preorder, inorder);
        System.out.println(root);
    }

    public TreeNode createBinaryTree(String[] preorder, String[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i].equals(preorder[0])) {
                // 找到左子树的根节点
                String[] preLeft = Arrays.copyOfRange(preorder, 1, i + 1);
                String[] postLeft = Arrays.copyOfRange(inorder, 0, i);
                root.left = createBinaryTree(preLeft, postLeft);
                // 找到右子树的根节点
                String[] preRight = Arrays.copyOfRange(preorder, i + 1, preorder.length);
                String[] postRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);
                root.right = createBinaryTree(preRight, postRight);
                break;
            }
        }
        return root;
    }

    // 根据中序遍历和后序遍历创建二叉树
    public TreeNode createBinaryTree2(String[] postorder, String[] inorder) {
        if (postorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i].equals(postorder[postorder.length - 1])) {
                // 找到左子树的根节点
                String[] postLeft = Arrays.copyOfRange(postorder, 0, i);
                String[] inLeft = Arrays.copyOfRange(inorder, 0, i);
                root.left = createBinaryTree2(postLeft, inLeft);
                // 找到右子树的根节点
                String[] postRight = Arrays.copyOfRange(postorder, i, postorder.length - 1);
                String[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);
                root.right = createBinaryTree2(postRight, inRight);
                break;
            }
        }
        return root;
    }

    @Test
    public void test7() {
        String[] preorder = {"1", "2", "4", "7", "3", "5", "6", "8"};
        String[] strings = Arrays.copyOfRange(preorder, preorder.length, preorder.length);
        String[] strings1 = Arrays.copyOfRange(preorder, 0, 0);
        System.out.println(Arrays.toString(strings));
        System.out.println(Arrays.toString(strings1));
    }


    private static class TreeNode<T> {
        T val;
        TreeNode left;
        TreeNode right;

        TreeNode(T x) {
            val = x;
        }

        TreeNode() {

        }

        TreeNode(TreeNode left, T x, TreeNode right) {
            this.left = left;
            this.right = right;
            val = x;
        }
    }
}
